package leetcode.code0336;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution2 implements IDebug {

	Integer emptyIndex;

	class Node {
		Node[] cs;
		Integer index;

		public Node() {
			cs = new Node[26];
			index = null;
		}

		public void add(String word, int index) {
			Node node = root;
			for (char c : word.toCharArray()) {
				int cur = c - 'a';
				if (node.cs[cur] == null) {
					node.cs[cur] = new Node();
				}
				node = node.cs[cur];
			}
			node.index = index;
		}
	}

	Node root;

	public List<List<Integer>> palindromePairs(String[] words) {
		emptyIndex = null;
		root = new Node();
		List<List<Integer>> ans = new ArrayList<>();
		for (int i = 0; i < words.length; i++) {
			String word = words[i];
			if (word.length() == 0) {
				emptyIndex = i;
			} else {
				root.add(word, i);
			}
		}
		for (int i = 0; i < words.length; i++) {
			String word = words[i];
			if (word.length() == 0) {
				continue;
			} else {
				this.longestPalindrome(word, i, ans);
			}
		}
		return ans;
	}

//  aabbaacbabc
//	[#,a,#,a,#,b,#,b,#,a,#,a,#,c,#,c,#,]
//	[1,2,3,2,1,2,7,2,1,2,3,2,1,2,3,2,1,]
	public void longestPalindrome(String s, int index, List<List<Integer>> ans) {
		char[] chars = this.sharp(s);//
		int[] radius = new int[chars.length];
		int center = -1;
		int range = -1;
		int start = -1;
		int end = -1;
		int len = chars.length;
		for (int i = 0; i < len; i++) {
			radius[i] = range > i ? Math.min(radius[((center) << 1) - i], range - i) : 1;
			while (i + radius[i] < len && i - radius[i] > -1 && chars[i + radius[i]] == chars[i - radius[i]]) {
				radius[i]++;
			}
			if (i + radius[i] > range) {
				range = i + radius[i];
				center = i;
			}
			start = i - radius[i] + 1;
			end = i + radius[i];// - 1
			boolean pre = start == 0;// 前半段回文
			boolean suf = end == len;// 后半段回文 - 1
			if (pre && suf) {
				if (emptyIndex != null) {
					ans.add(Arrays.asList(index, this.emptyIndex));
					ans.add(Arrays.asList(this.emptyIndex, index));
				}
			}
			if (pre && end > 1 && end != len) {
//				System.out.println("前回文" + start + " " + end);
				Integer leftIndex = this.find(chars, end, len);
				if (leftIndex != null) {
					ans.add(Arrays.asList(leftIndex, index));
				}
			}
			if (suf && start < len - 1 && start != 0) {
//				System.out.println("后全回文" + start + " " + end);
				Integer rightIndex = this.find(chars, 1, start);
				if (rightIndex != null) {
					ans.add(Arrays.asList(index, rightIndex));
				}
			}

		}
		Integer allIndex = this.find(chars, 1, len);
		if (allIndex != null && allIndex != index) {
			ans.add(Arrays.asList(allIndex, index));
		}
//		H.printObject(chars);
//		H.printObject(radius);
	}

	private Integer find(char[] chars, int start, int len) {
		Node node = root;
		for (int i = len - 1; i >= start; i--) {
			char c = chars[i];
			if (c == '#') {
				continue;
			}
			int index = c - 'a';
			if (node.cs[index] == null) {
				return null;
			}
			node = node.cs[index];
		}
		return node.index;
	}

	private char[] sharp(String s) {
		char[] chars = new char[(s.length() << 1) | 1];
		int p = 0;
		for (int i = 0; i < chars.length; i++) {
			if ((i & 1) == 0) {
				chars[i] = '#';
			} else {
				chars[i] = s.charAt(p++);
			}
		}
		return chars;
	}

	@Override
	public void debug1() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[0,1],[1,0],[3,2],[2,4]]");
		HelpDebug.compare(e, this.palindromePairs(HelpDebug.str2array2("[\"abcd\",\"dcba\",\"lls\",\"s\",\"sssll\"]")));
	}

	@Override
	public void debug2() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[0,1],[1,0]]");
		HelpDebug.compare(e, this.palindromePairs(HelpDebug.str2array2("[\"bat\",\"tab\",\"cat\"]")));
	}

	@Override
	public void debug3() {
		List<List<Integer>> e = HelpDebug.str2intlist1("[[0,1],[1,0]]");
		HelpDebug.compare(e, this.palindromePairs(HelpDebug.str2array2("[\"a\",\"\"]")));
	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
//		so.debug2();
//		so.debug3();
//		so.debug4();

//		System.out.println(so.longestPalindrome("abcddcbaabcddcba"));
//		System.out.println(so.longestPalindrome("abba"));

//		List<List<Integer>> ans = new ArrayList<>();
//		System.out.println("aabbaacbabc");
//		so.longestPalindrome("aabbaacbabc", 1, ans);
//		System.out.println("aba");
//		so.longestPalindrome("aba", 1, ans);
//		H.printObject(ans);
	}

}
